{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十一题 IP地址转化\n",
    "    IP地址是一个用'.'隔开的四段数字，请你把IP地址转换成一个整数(IPv4)\n",
    "    例如：114.55.207.244的二进制表示是01110010 00110111 11001111 11110100，其十进制表示是1916260340"
   ],
   "id": "37e2afb868b7394f"
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-03-07T00:26:44.293600Z",
     "start_time": "2025-03-07T00:26:44.280710Z"
    }
   },
   "source": [
    "def func(str):\n",
    "    strs=str.split('.')\n",
    "    res=''\n",
    "    for i in strs:\n",
    "        #十进制转二进制高位补0\n",
    "        #'{:08b}'.format(val)\n",
    "        res+='{:08b}'.format(int(i))#1.将字符串i转换为整数2.将整数转换为8位的二进制字符串，不足8位时在前面补零3.将这个字符串拼接到结果中\n",
    "    return int(res,2)  #将拼接好的二进制字符串res转换位对应的十进制整数     res：需要转换的值  2：基数，表示二进制    int()可以将一个字符串表示的数字从指定的进制转换为是十进制整数，通过传递第二个参数（基数）来实现\n",
    "print(func('114.55.207.244'))"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1916260340\n"
     ]
    }
   ],
   "execution_count": 2
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "def func(str):\n",
    "    strs=str.split('.')\n",
    "    res=''\n",
    "    for i in strs:\n",
    "        res+='{08b}'.format(int(i))\n",
    "    return int(res,2)"
   ],
   "id": "91d0711d29d8f732"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十二题 二分查找（一）\n",
    "    请实现无重复数字的升序数组的二分查找\n",
    "    给定一个元素升序的、无重复数字的整型数组nums和一个目标值target，写一个函数搜索nums中target,如果目标值存在返回下标（下标从0开始），否则返回-1"
   ],
   "id": "5afd7f4309ad9d40"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-07T00:48:58.818137Z",
     "start_time": "2025-03-07T00:48:58.791506Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(nums,target):\n",
    "    left=0\n",
    "    right=len(nums)-1\n",
    "    #从数组首尾开始，直到两指针相遇\n",
    "    while left<=right:\n",
    "        middle=int((left+right)/2)\n",
    "        if nums[middle]==target:\n",
    "            return middle\n",
    "        if nums[middle]>target:\n",
    "            right=middle-1\n",
    "        else:\n",
    "            left =middle+1\n",
    "    return -1\n",
    "list=[1,3,5,7,9]\n",
    "target=6\n",
    "print(func(list,target))"
   ],
   "id": "1f656515c63b889",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n"
     ]
    }
   ],
   "execution_count": 5
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十三题 二分查找（二）\n",
    "    请实现重复数字的升序数组的二分查找\n",
    "    给定一个元素有序的（升序）长度为n的整型数组nums和一个目标值target，写一个函数搜索nums中第一个出现的target,如果目标值存在返回下标（下标从0开始），否则返回-1"
   ],
   "id": "bd0d7bb61732e611"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-07T14:52:10.350561Z",
     "start_time": "2025-03-07T14:52:10.296454Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(nums,target):\n",
    "    left=0\n",
    "    right=len(nums)-1\n",
    "    while left<=right:\n",
    "        middle=(left+right)//2\n",
    "        if nums[middle]>target:\n",
    "            right=middle-1\n",
    "        elif nums[middle]<target:\n",
    "            left=middle+1\n",
    "        else:\n",
    "            temp=middle\n",
    "            while nums[temp]==target and temp>=0:\n",
    "                temp-=1\n",
    "            return temp+1\n",
    "    return -1\n",
    "list=[1,2,2,2,2,4]\n",
    "target=2\n",
    "print(func(list,2))\n",
    "    "
   ],
   "id": "41bd166a4512a91c",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "execution_count": 9
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十四题 移动0\n",
    "    给定一个数组，请你实现将所有0移动到数组末尾并且不改变其他数字的相对顺序"
   ],
   "id": "203325143d6e0855"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-07T14:57:19.402506Z",
     "start_time": "2025-03-07T14:57:19.377636Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#pop之后数组下标发生改变了不能这样做\n",
    "# def func(nums):\n",
    "#     for i in nums:\n",
    "#         if i==0:\n",
    "#             nums.pop(i)\n",
    "#             nums.append(i)\n",
    "#     return nums\n",
    "# list=[0,1,5,0,6,2,0,8]\n",
    "# print(func(list))"
   ],
   "id": "88c3eee59a1de4b3",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 8, 0, 0, 0, 0, 0, 0]\n"
     ]
    }
   ],
   "execution_count": 10
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-07T15:02:49.623158Z",
     "start_time": "2025-03-07T15:02:49.596994Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(nums):\n",
    "    for i in nums:\n",
    "        if i==0:\n",
    "            nums.remove(i)\n",
    "            nums.append(0)\n",
    "    return nums\n",
    "list=[0,1,5,0,6,2,0,8]\n",
    "print(func(list))"
   ],
   "id": "fb8e95bedb71afa7",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 6, 2, 8, 0, 0, 0]\n"
     ]
    }
   ],
   "execution_count": 11
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十五题 旋转字符串\n",
    "    字符串旋转：\n",
    "    给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true"
   ],
   "id": "d32a434787ce59a9"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-07T23:56:09.835691Z",
     "start_time": "2025-03-07T23:56:09.820426Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#hello->llohe\n",
    "#拼接之后 hellohello  llohe在这个拼接之后的字符串里\n",
    "def func(a,b):\n",
    "    if len(a) != len(b):  #长度不等肯定不能\n",
    "        return False\n",
    "    else:\n",
    "        bigA=a+a\n",
    "        result = b in bigA\n",
    "        return result\n",
    "print(func('hello','lloh'))"
   ],
   "id": "3a0c4cf796ed92d0",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "execution_count": 12
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十六题 判断子序列\n",
    "    给定两个字符串S和T，判断S是否是T的子序列。\n",
    "    即是否可以从T删除一些字符转换成S"
   ],
   "id": "32707961c222fea4"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T00:34:55.126490Z",
     "start_time": "2025-03-08T00:34:55.096180Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(s,t):\n",
    "    n=0\n",
    "    c=''\n",
    "    if len(s)>len(t):\n",
    "        return False\n",
    "    for i in t:  \n",
    "        if i==s[n]:   #主要是这里\n",
    "            c+=i\n",
    "            n+=1\n",
    "    if s==c:\n",
    "        return True\n",
    "    return  False\n",
    "print(func('hlo','hello'))"
   ],
   "id": "6226c4bdef57426d",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "execution_count": 13
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十七题\n",
    "    在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3.存在不合法的输入的话输出-1"
   ],
   "id": "8abf8694a664177e"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T00:38:46.797005Z",
     "start_time": "2025-03-08T00:38:46.785194Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(nums):\n",
    "    for i in nums:\n",
    "        if nums.count(i)>=2:\n",
    "            return i\n",
    "    return -1\n",
    "print(func([1,2,2,3,4,5,5]))\n",
    "print(func([1,2,3,4]))"
   ],
   "id": "a04983bc1f986613",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "-1\n"
     ]
    }
   ],
   "execution_count": 15
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十八题 字符串的相邻字符去重\n",
    "    给定一个仅由英文小写字母组成的字符串ss,将相邻且相同的两个字符删掉构成新的字符串，重复删除操作直至生成不符合删除条件的字符串并返回  \n",
    "    输入：'acbbc'\n",
    "    输出：'a'"
   ],
   "id": "b8b565ff833dad58"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T00:50:05.825405Z",
     "start_time": "2025-03-08T00:50:05.815722Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def func(s):\n",
    "    res=''\n",
    "    for i in s:\n",
    "        if res=='':\n",
    "            res+=i\n",
    "        elif i==res[-1]:\n",
    "            res=res[:-1]\n",
    "        else:\n",
    "            res+=i\n",
    "    return res\n",
    "print(func('acbbc'))\n",
    "print(func('abcd'))"
   ],
   "id": "7c21451aeabc5bf",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "abcd\n"
     ]
    }
   ],
   "execution_count": 20
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第六十九题 2的幂\n",
    "    给定一个非负整数n,请问是否存在一个x满足2^x=n,如果有，则返回true，否则返回false"
   ],
   "id": "a728d99cde1a8b7e"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T01:01:05.254065Z",
     "start_time": "2025-03-08T01:01:02.879276Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#可以一直除二\n",
    "n=int(input())\n",
    "\n",
    "def func(n):\n",
    "    num=n\n",
    "    for i in range(n):\n",
    "        num=num/2\n",
    "        if num==1:\n",
    "            return('true')\n",
    "        elif num<1:\n",
    "            return 'false'\n",
    "        \n",
    "    else:\n",
    "        return 'false'\n",
    "\n",
    "print(func(n))   \n",
    "\n"
   ],
   "id": "987ffc745a3f898e",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n"
     ]
    }
   ],
   "execution_count": 28
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T01:22:00.947613Z",
     "start_time": "2025-03-08T01:22:00.934949Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#位运算\n",
    "#按位取反：~每个二进制进行取反操作\n",
    "#按位与：& 1&1=1，其它都为0\n",
    "#按位或：| 0|0=0，其它都为1\n",
    "#按位异或：^相同“0”，不同“1”\n",
    "#0100(4)  1000(8)  \n",
    "#0011(3)  0111(7)\n",
    "#4&3=0000  8&7=0000\n",
    "# 如果一个数是二的幂，那么它一定只有一个1\n",
    "#一个数和它小1的数做与运算是零的话，这个数是2的幂\n",
    "def func(n):\n",
    "    return n>0 and n&(n-1)==0\n",
    "print(func(8))\n",
    "print(func(3))\n",
    "    "
   ],
   "id": "541392114e902739",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "execution_count": 33
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T01:20:01.725064Z",
     "start_time": "2025-03-08T01:20:01.698251Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#这个是题外话，str.find()\n",
    "str1=\"liuyuxiao\"\n",
    "print(str1.find(\"i\",4,8))\n"
   ],
   "id": "4fd8d4b800c1d99f",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "execution_count": 32
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 第七十题 最长公共子串\n",
    "    给定两个字符串str1和str2，输出两个字符串的最长公共字符串，保证str1和str2的最长公共字串存在且唯一"
   ],
   "id": "dbba7445cddf7d90"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-08T01:33:55.483314Z",
     "start_time": "2025-03-08T01:33:55.473378Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 找到一个匹配的右指针往右挪，找不到匹配的，都往右挪\n",
    "def lcs(str1,str2):\n",
    "    res=''\n",
    "    left=0\n",
    "    for i in range(len(str1)+1):  #因为要切片操作，后面那个取不到\n",
    "        if str1[left:i+1] in str2:\n",
    "            res=str1[left:i+1]\n",
    "        else:\n",
    "            left+=1\n",
    "    return res\n",
    "print(lcs('hellopython','goodlopylike'))"
   ],
   "id": "d1cec47b0a2165c",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lopy\n"
     ]
    }
   ],
   "execution_count": 34
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": "",
   "id": "739473869571dab6"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
